package org.hhchat.leetcode.sort;

import java.util.*;

/**
 * Created this one by HMH on 2017/5/27.
 */
public class code350 {
    public static class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Map<Integer, Integer> nums1Map = getMap(nums1);
            Map<Integer, Integer> nums2Map = getMap(nums2);
            //check
            List<Integer> result = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entity : nums1Map.entrySet()) {
                int key = entity.getKey();
                Integer count1 = entity.getValue();
                Integer count2 = nums2Map.get(key);
                if ( count2 == null || count2 == 0) {
                    continue;
                }
                else{
                    int count = count1 > count2 ? count2 : count1;
                    while (count-->0) {
                        result.add(key);
                    }
                }
            }
            int[] resultArr = new int[result.size()];
            for(int i=0;i<result.size();i++) {
                resultArr[i] = result.get(i);
            }
            return resultArr;
        }

        public Map<Integer, Integer> getMap(int[] nums) {
            Map<Integer, Integer> maps = new HashMap<>();
            for (int now : nums) {
                Integer count = maps.get(now);
                if (count == null) {
                    count = 1;
                    maps.put(now, count);
                } else {
                    maps.put(now, count + 1);
                }
            }
            return maps;
        }

        public static void main(String[] args){
            int[] a = new int[]{1, 2, 2, 1};
            int[] b = new int[]{2, 2};
            Solution solution = new Solution();
            int[] result = solution.intersect(a, b);
            System.out.println(Arrays.toString(result));
        }
    }
}

/*
 * 排序解法：先排序，从小到大搜索，两个队首如果一样就添加到结果列表中，如果不相同就往下索引
 */

//public class Solution {
//    public int[] intersect(int[] nums1, int[] nums2) {
//        Arrays.sort(nums1);
//        Arrays.sort(nums2);
//        int p1 = 0;
//        int p2 = 0;
//        List <Integer> s = new ArrayList<>();
//        while(p1 < nums1.length && p2 < nums2.length){
//            if (nums1[p1] == nums2[p2]){
//                s.add(nums1[p1]);
//                p1 ++;
//                p2 ++;
//            }
//
//
//            else if (nums1[p1] < nums2[p2])
//                p1 ++;
//            else
//                p2 ++;
//        }
//        int [] r = new int[s.size()];
//        for (int i =0; i < s.size(); i++){
//            r[i] = s.get(i);
//        }
//        return r;
//    }
//}